//
// Description: Kruskal算法 模板
// Created by Loading on 2022/5/26.
//

/* 适用于求一个带权无向图的最小生成树，所谓最小生成树：指使用全部 n 个顶点和 n - 1 条边构成的边权之和最小的无向连通图 */

/*
 * 算法思想：Kruskal（克鲁斯卡尔）算法，主旨在于结合并查集，维护一个祖先节点的集合
 * 首先将所有边按照权重由小到大排序，并将每个点的祖先节点指向自己，遍历排序后的边，
 * 1、若发现边的两个节点的祖先节点不一致，则累加该边的权重，并合并两个节点的祖先，并做路径压缩操作；
 * 2、若发现边的两个节点的祖先一致，则两个节点一定已经在最小生成树中，无需再增加此条边，否则会出现环路。
 */

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 2e5 + 10;
constexpr int INF = 0x3f3f3f3f;

int father[N]; // 祖先节点
int n, m;

// 使用 struct 储存边
struct Edges {
    int a, b, w;

    bool operator<(const Edges &E) const {
        return w < E.w;
    }
} edges[N];

/* 并查集核心操作 */
// 查找 x 的祖先节点 + 路径压缩
int find(int x) {
    if (father[x] != x) {
        father[x] = find(father[x]);
    }
    return father[x];
}

/* Kruskal，时间复杂度：O(mlogm)，m 表示边数 */
int kruskal() {
    // 初始化祖先节点
    for (int i = 1; i <= n; ++i) {
        father[i] = i;
    }
    // 将边按权重排序
    sort(edges, edges + m);

    int res = 0; // 最小生成树中所有边的权重之和
    int cnt = 0; // 集合中有多少条边
    // 遍历每条边
    for (int i = 0; i < m; ++i) {
        int a = edges[i].a;
        int b = edges[i].b;
        int w = edges[i].w;
        // 寻找两个节点的祖先节点
        a = find(a), b = find(b);
        if (a != b) {
            father[a] = b;
            res += w;
            ++cnt;
        }
    }

    // 集合中的边数 < n - 1，必然不连通
    if (cnt < n - 1) {
        return INF;
    }
    return res;
}

int main() {

    return 0;
}